package com.huawei_exam.greedy_algorithm;

/**
 *55. 跳跃游戏
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 判断你是否能够到达最后一个下标。
 */
public class S55 {
    public static void main(String[] args) {
        int[] array1 = {3,2,1,0,4};
        int[] array2 = {2,3,1,1,4};
        System.out.println(F1(array1));
        System.out.println(F1(array2));
        System.out.println(F2(array1));
        System.out.println(F2(array2));
    }
    /***
     *  动态规划
     *  性质：1、能到达某个位置：该位置之前存在最远达到点大于这个位置的点
     *  遍历每个点
     *  存储能达到的点：动态规划
     *  遍历该点之前的点：能到达的点是否能达到该点
     */
    public static boolean F1(int[] array) {
        boolean[] dp = new boolean[array.length];
        dp[0] = true;
        for (int i = 1; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + array[j] >= i) {
                    dp[i] = true;
                }
            }
        }
        return dp[array.length - 1];
    }
    /***
     *  贪心算法：当前情况的解——>遍历——>所有情况
     *  性质：某个点跳最远的点之前的点都能到达
     */
    public static boolean F2(int[] array) {
        if (array.length == 1) return true;
        int cover = array[0];
        for (int i = 0; i < cover; i++) {
            cover = Math.max(cover,i + array[i]);
            if (cover >= array.length - 1) return true;
        }
        return false;
    }
}
